We established that the powerful $O(\log_2 n)$ efficiency of Divide-and-Conquer comes from immediately eliminating half the search space. This efficiency is the core promise of Binary Search.
- Binary Search is an algorithm designed to efficiently find a target value $t$ within a data set of size $n$. It is the canonical example of the Divide-and-Conquer strategy applied to searching.
- Critical Requirement: Binary Search MUST operate on a sorted array $A$. If the data is unsorted, this algorithm cannot guarantee correctness.
- The mechanism relies on three core steps in each iteration:
- 1. Pivot Selection: Identify the middle element of the current search interval (the pivot).
- 2. Comparison: Compare the pivot against the target $t$.
- 3. Division: If the pivot is not $t$, discard half of the remaining search space based on the comparison result.
- This constant halving ensures that the worst-case time complexity remains $O(\log_2 n)$, providing massive performance benefits over linear $O(n)$ search as $n$ grows.
Binary Search Properties
| Property | Description | Complexity |
|---|---|---|
| Data Structure | Must be a sorted array. | N/A |
| Time (Worst) | Target is last element or not present. | $O(\log n)$ |
| Time (Best) | Target is the middle element. | $O(1)$ |
| Space (Iterative) | Uses constant extra space for pointers. | $O(1)$ |